#ifndef SKIPLIST_H
#define SKIPLIST_H

#include <cmath>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <mutex>

// 定义默认持久化文件路径（未实际使用，被序列化字符串替代）
#define STORE_FILE "store/dumpFile"
// 键值对分隔符
static std::string delimiter = ":";

// 模板类：跳表节点
template <typename K, typename V>
class Node {
public:
    Node() {}  // 默认构造函数
    Node(K k, V v, int level);  // 带参构造函数（初始化键、值、层级）
    ~Node();  // 析构函数

    K get_key() const;      // 获取键
    V get_value() const;    // 获取值
    void set_value(V);      // 修改值

    // 存储各层级下一个节点的指针数组（层级从0到node_level）
    Node<K, V> **forward;
    int node_level;  // 节点当前的层级

private:
    K key;  // 键
    V value;  // 值
};

// 节点构造函数：初始化键、值、层级，并为forward数组分配内存
template <typename K, typename V>
Node<K, V>::Node(const K k, const V v, int level) {
    this->key = k;
    this->value = v;
    this->node_level = level;
    // 层级+1：因为数组索引从0到level
    this->forward = new Node<K, V>* [level + 1];
    // 初始化forward数组为NULL
    memset(this->forward, 0, sizeof(Node<K, V> *) * (level + 1));
};

// 节点析构函数：释放forward数组内存
template <typename K, typename V>
Node<K, V>::~Node() {
    delete[] forward;
};

// 获取键
template <typename K, typename V>
K Node<K, V>::get_key() const {
    return key;
};

// 获取值
template <typename K, typename V>
V Node<K, V>::get_value() const {
    return value;
};

// 修改值
template <typename K, typename V>
void Node<K, V>::set_value(V value) {
    this->value = value;
};

template <typename K, typename V>
class SkipListDump {
public:
    // 允许Boost序列化访问私有成员
    friend class boost::serialization::access;

    // 序列化函数：将键值向量写入归档
    template <class Archive>
    void serialize(Archive &ar, const unsigned int version) {
        ar &keyDumpVt_;  // 序列化键向量
        ar &valDumpVt_;  // 序列化值向量
    }

    std::vector<K> keyDumpVt_;  // 存储所有节点的键
    std::vector<V> valDumpVt_;  // 存储所有节点的值

public:
    // 向持久化对象中插入节点的键值
    void insert(const Node<K, V> &node);
};

// 插入节点的键和值到向量中
template <typename K, typename V>
void SkipListDump<K, V>::insert(const Node<K, V> &node) {
    keyDumpVt_.emplace_back(node.get_key());    // 插入键
    valDumpVt_.emplace_back(node.get_value());  // 插入值
}

template <typename K, typename V>
class SkipList {
public:
    SkipList(int);      // 构造函数（指定最大层级）
    ~SkipList();        // 析构函数
    int get_random_level();     // 生成随机层级（用于新节点）
    Node<K, V> *create_node(K, V, int);  // 创建新节点
    int insert_element(K, V);   // 插入元素（存在则返回1，否则返回0）
    void display_list();        // 打印跳表结构
    bool search_element(K, V &value);  // 查找元素（找到则赋值value并返回true）
    void delete_element(K);     // 删除元素
    void insert_set_element(K &, V &);  // 插入或更新元素（存在则覆盖）
    std::string dump_file();    // 序列化跳表为字符串
    void load_file(const std::string &dumpStr);  // 从序列化字符串加载跳表
    void clear(Node<K, V> *);   // 递归删除节点（用于析构）
    int size();  // 返回跳表元素数量

private:
    // 从字符串中解析键和值（格式："key:value"）
    void get_key_value_from_string(const std::string &str, std::string *key, std::string *value);
    // 验证字符串是否符合"key:value"格式
    bool is_valid_string(const std::string &str);

private:
    int _max_level;         // 跳表最大允许层级
    int _skip_list_level;   // 跳表现有最高层级
    Node<K, V> *_header;    // 头节点（哨兵节点，不存储实际数据）
    int _element_count;     // 元素总数
    std::mutex _mtx;        // 互斥锁（保证线程安全）
};

// 创建新节点并返回指针
template <typename K, typename V>
Node<K, V> *SkipList<K, V>::create_node(const K k, const V v, int level) {
    Node<K, V> *n = new Node<K, V>(k, v, level);
    return n;
}

// 插入元素：存在返回1，成功插入返回0
template <typename K, typename V>
int SkipList<K, V>::insert_element(const K key, const V value) {
    _mtx.lock();  // 加锁保证线程安全
    Node<K, V> *current = this->_header;

    // update数组：存储各层级中需要修改指针的节点
    Node<K, V> *update[_max_level + 1];
    memset(update, 0, sizeof(Node<K, V> *) * (_max_level + 1));

    // 从最高层开始向下查找插入位置
    for (int i = _skip_list_level; i >= 0; i--) {
        // 移动到当前层级中小于目标键的最后一个节点
        while (current->forward[i] != NULL && current->forward[i]->get_key() < key) {
            current = current->forward[i];
        }
        update[i] = current;  // 记录当前层级的前驱节点
    }

    // 到达第0层，检查当前节点是否已存在
    current = current->forward[0];
    if (current != NULL && current->get_key() == key) {
        std::cout << "key: " << key << ", exists" << std::endl;
        _mtx.unlock();
        return 1;  // 元素已存在
    }

    // 插入新节点
    if (current == NULL || current->get_key() != key) {
        // 为新节点生成随机层级
        int random_level = get_random_level();

        // 如果随机层级高于当前最大层级，更新update数组（指向头节点）
        if (random_level > _skip_list_level) {
            for (int i = _skip_list_level + 1; i < random_level + 1; i++) {
                update[i] = _header;
            }
            _skip_list_level = random_level;  // 更新跳表最高层级
        }

        // 创建新节点并插入各层级
        Node<K, V> *inserted_node = create_node(key, value, random_level);
        for (int i = 0; i <= random_level; i++) {
            inserted_node->forward[i] = update[i]->forward[i];  // 新节点指向原前驱节点的下一个节点
            update[i]->forward[i] = inserted_node;  // 前驱节点指向新节点
        }

        std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl;
        _element_count++;  // 元素计数+1
    }

    _mtx.unlock();
    return 0;
}

// 按层级打印跳表中的所有元素
template <typename K, typename V>
void SkipList<K, V>::display_list() {
    std::cout << "\n*****Skip List*****" << "\n";
    for (int i = 0; i <= _skip_list_level; i++) {
        Node<K, V> *node = this->_header->forward[i];
        std::cout << "Level " << i << ": ";
        while (node != NULL) {
            std::cout << node->get_key() << ":" << node->get_value() << ";";
            node = node->forward[i];
        }
        std::cout << std::endl;
    }
}

// 将跳表数据序列化为字符串（使用Boost库）
template <typename K, typename V>
std::string SkipList<K, V>::dump_file() {
    Node<K, V> *node = this->_header->forward[0];  // 从第0层遍历所有节点
    SkipListDump<K, V> dumper;
    while (node != nullptr) {
        dumper.insert(*node);  // 收集所有节点的键值
        node = node->forward[0];
    }

    // 序列化到字符串流
    std::stringstream ss;
    boost::archive::text_oarchive oa(ss);
    oa << dumper;
    return ss.str();
}

// 从序列化字符串加载跳表数据
template <typename K, typename V>
void SkipList<K, V>::load_file(const std::string &dumpStr) {
    if (dumpStr.empty()) return;

    // 反序列化
    SkipListDump<K, V> dumper;
    std::stringstream iss(dumpStr);
    boost::archive::text_iarchive ia(iss);
    ia >> dumper;

    // 插入所有键值对（注：原代码此处有误，应为valDumpVt_[i]）
    for (int i = 0; i < dumper.keyDumpVt_.size(); ++i) {
        insert_element(dumper.keyDumpVt_[i], dumper.valDumpVt_[i]);  // 修正后的值向量
    }
}

// 返回元素数量
template <typename K, typename V>
int SkipList<K, V>::size() {
    return _element_count;
}

// 删除元素
template <typename K, typename V>
void SkipList<K, V>::delete_element(K key) {
    _mtx.lock();
    Node<K, V> *current = this->_header;
    Node<K, V> *update[_max_level + 1];
    memset(update, 0, sizeof(Node<K, V> *) * (_max_level + 1));

    // 查找各层级的前驱节点
    for (int i = _skip_list_level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->get_key() < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];
    if (current != NULL && current->get_key() == key) {
        // 从各层级删除节点
        for (int i = 0; i <= _skip_list_level; i++) {
            if (update[i]->forward[i] != current) break;  // 该层级无此节点，停止
            update[i]->forward[i] = current->forward[i];
        }

        // 更新跳表最高层级（移除空层级）
        while (_skip_list_level > 0 && _header->forward[_skip_list_level] == 0) {
            _skip_list_level--;
        }

        std::cout << "Successfully deleted key " << key << std::endl;
        delete current;
        _element_count--;
    }

    _mtx.unlock();
}

// 插入或更新元素（存在则先删除再插入）
template <typename K, typename V>
void SkipList<K, V>::insert_set_element(K &key, V &value) {
    V oldValue;
    if (search_element(key, oldValue)) {
        delete_element(key);  // 存在则删除
    }
    insert_element(key, value);  // 插入新值
}

// 查找元素
template <typename K, typename V>
bool SkipList<K, V>::search_element(K key, V &value) {
    std::cout << "search_element-----------------" << std::endl;
    Node<K, V> *current = _header;

    // 从最高层向下查找
    for (int i = _skip_list_level; i >= 0; i--) {
        while (current->forward[i] && current->forward[i]->get_key() < key) {
            current = current->forward[i];
        }
    }

    // 检查第0层的节点
    current = current->forward[0];
    if (current && current->get_key() == key) {
        value = current->get_value();
        std::cout << "Found key: " << key << ", value: " << current->get_value() << std::endl;
        return true;
    }

    std::cout << "Not Found Key:" << key << std::endl;
    return false;
}

// 构造函数：初始化跳表参数
template <typename K, typename V>
SkipList<K, V>::SkipList(int max_level) {
    this->_max_level = max_level;
    this->_skip_list_level = 0;  // 初始层级为0
    this->_element_count = 0;

    // 创建头节点（键值为默认值，层级为最大层级）
    K k;
    V v;
    this->_header = new Node<K, V>(k, v, _max_level);
};

// 析构函数：释放资源
template <typename K, typename V>
SkipList<K, V>::~SkipList() {
    // 递归删除所有节点
    if (_header->forward[0] != nullptr) {
        clear(_header->forward[0]);
    }
    delete (_header);  // 释放头节点
}

// 递归删除节点（从第0层开始）
template <typename K, typename V>
void SkipList<K, V>::clear(Node<K, V> *cur) {
    if (cur->forward[0] != nullptr) {
        clear(cur->forward[0]);  // 先删除下一个节点
    }
    delete (cur);  // 再删除当前节点
}

// 生成随机层级（1到_max_level之间，概率上每层减半）
template <typename K, typename V>
int SkipList<K, V>::get_random_level() {
    int k = 1;
    while (rand() % 2) {  // 50%概率增加层级
        k++;
    }
    // 层级不超过最大限制
    k = (k < _max_level) ? k : _max_level;
    return k;
};

#endif  // SKIPLIST_H